/*
 * @Author: szx
 * @Date: 2022-04-09 14:24:04
 * @LastEditTime: 2022-04-09 14:45:46
 * @Description:
 * @FilePath: \leetcode\剑指offerII\050\050.js
 */

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function (root, targetSum) {
    const prefix = new Map();
    prefix.set(0, 1);
    const dfs = (root, sum) => {
        if (!root) return 0;
        let res = 0;
        sum += root.val;
        res = prefix.get(sum - targetSum) || 0;
        prefix.set(sum, (prefix.get(sum) || 0) + 1);
        res += dfs(root.left, sum);
        res += dfs(root.right, sum);
        prefix.set(sum, (prefix.get(sum) || 0) - 1);
        return res;
    };
    return dfs(root, 0);
};
